
using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Ack
{
	public class NesEncoderParameters
	{
		public bool EnableHuffman;
		public bool AllowColorRemap;
	}
	
	public class NesEncoder2
	{
		private int EncodeRowDifferences(ulong p, ulong r, byte[] output, int lowestCost)
		{
			// Early-out: identical patterns.
			if(r == p)
			{
				output[0] = 0;
				output[1] = 0;
				return 2;
			}
						
			ulong diff = r ^ p;

			// Early-out: No zero-bytes means also not possible to encode under 10 bytes.
			if(!Misc.HasZeroByte(diff))
			{
				return Int32.MaxValue;
			}
			
			int len = 2;
			output[0] = 0; // header 1 (reserved for RD scheme)
			output[1] = 0; // header 2 (set bit = row is explicitly stored)

			// Take diff byte-for-byte
			byte mask = 1 << 7;
			for(int pshift = 0; pshift < 64; pshift += 8, mask >>= 1)
			{
				byte bdiff = (byte)(diff >> pshift);
				if(bdiff != 0)
				{
					output[len++] = (byte)(p >> pshift);
					
					if(len >= lowestCost) 
						return Int32.MaxValue;

					output[1] |= mask;
				}
			}
				
			return len;
		}
		
		private byte[] EncodeRD(int patternIndex, out PatternMode mode)
		{
			byte[] tempRD = new byte[10];
			byte[] bestRD = new byte[10];
			int bestRDLength = Int32.MaxValue;
			
			ulong[][] patternTables = { _patterns, _patternsRX, _patternsRY, _patternsRXY };
							
			mode = PatternMode.RD;
			
			//for(int transposed = 0; transposed < 2; ++transposed)
			for(int tbl = 0; tbl < 4; ++tbl)
			{
				for(int i = 0; i <= 127; ++i)
				{
					int referenceIndex = patternIndex-i-1;
					
					if(bestRDLength == 2 || referenceIndex < 0)
						break;
				
					ulong p = _patterns[patternIndex];
					ulong r = patternTables[tbl][referenceIndex];
					int len = EncodeRowDifferences(p, r, tempRD, bestRDLength);
					
					if(len < bestRDLength)
					{
						bestRDLength = len;
						tempRD.CopyTo(bestRD,0);
						
						if((tbl & 2) != 0)
							mode = PatternMode.RD2;
						
						bestRD[0] = (byte)i;

						if((tbl & 1) != 0)
							bestRD[0] |= 0x80;
					}
				}
			}
			
			if(bestRDLength < 8)
			{				
				return Misc.TrimArray(bestRD,bestRDLength);
			}
			
			return null;
		}
		
		private int[] GetCommonPatterns()
		{
			Dictionary<ulong, int> firstIndex = new Dictionary<ulong, int>();
			Dictionary<ulong, int> freqs = new Dictionary<ulong, int>();
			for(int pi = 0; pi < _patterns.Length; ++pi)
			{
				ulong key = _patterns[pi];
				if(!freqs.ContainsKey(key))
				{
					firstIndex.Add(key,pi);
					freqs.Add(key,1);
				}
				else
					freqs[key]++;
			}
			
			var topTwo = (from entry in freqs orderby entry.Value descending select entry.Key).Take(2).ToArray();
			
			return new int[] {	topTwo.Length > 0 ? firstIndex[topTwo[0]] : -1,
								topTwo.Length > 1 ? firstIndex[topTwo[1]] : -1 };
		}
		
		enum PatternMode
		{
			// Modes for encoding a new pattern:
			Raw					= 0, // pattern is stored raw (8 bytes)
			RCR					= 1, // pattern uses row/column-repeat encoding (1+n bytes)
			
			// Modes for encoding a known pattern:
			CommonA				= 2, // a two-entry dictionary of "common" patterns is built.
			CommonB				= 3, // 
			
			SameAsLast			= 4, // pattern is equal to the last one
			SameAsLastInverted	= 5, // pattern is equal to the last one but bitwise inverted
			
			RD					= 6, 
			RD2					= 7  // pattern is based on reference pattern + differing rows (2+n bytes)
		};

		public class Statistics
		{
			public int _totalPatternCount;
			public int[] _patternModeCounts = new int[] {0,0,0,0,0,0,0,0};
			public int[] _mode67Counts = new int[] {0,0,0,0};
			public int _oneBitEligible;

			public void Add(Statistics other)
			{
				_oneBitEligible += other._oneBitEligible;
				_totalPatternCount += other._totalPatternCount;
				for(int i = 0; i < _patternModeCounts.Length; ++i)
					_patternModeCounts[i] += other._patternModeCounts[i];
				for(int i = 0; i < _mode67Counts.Length; ++i)
					_mode67Counts[i] += other._mode67Counts[i];
			}
			
			public override string ToString()
			{
				string s = "";
				s += "\n2 ) CommonA: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.CommonA]/_totalPatternCount);
				s += "\n3 ) CommonB: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.CommonB]/_totalPatternCount);
				s += "\n4 ) SameAsLast: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.SameAsLast]/_totalPatternCount);
				s += "\n5 ) SameAsLastInverted: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.SameAsLastInverted]/_totalPatternCount);
				
				s += "\n6a) RD: " + String.Format("{0:0.00%}",(float)_mode67Counts[0]/_totalPatternCount);
				s += "\n6b) RD(-x): " + String.Format("{0:0.00%}",(float)_mode67Counts[1]/_totalPatternCount);
				s += "\n7a) RD(-y): " + String.Format("{0:0.00%}",(float)_mode67Counts[2]/_totalPatternCount);
				s += "\n7b) RD(-x,-y): " + String.Format("{0:0.00%}",(float)_mode67Counts[3]/_totalPatternCount);
				
				s += "\n1 ) RCR: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.RCR]/_totalPatternCount);
				s += "\n0 ) Raw: " + String.Format("{0:0.00%}",(float)_patternModeCounts[(int)PatternMode.Raw]/_totalPatternCount);
				s += "\n1bite: " + String.Format("{0:0.00%}",(float)_oneBitEligible/_patternModeCounts[(int)PatternMode.Raw]);
				return s;
			}
		};
		
		public byte[] RemapColors(byte[] input, int[] map)
		{
			byte[] output = new byte[input.Length];
			for(int ti = 0; ti < input.Length/16; ++ti)
			{
				for(int y = 0; y < 8; ++y)
				{
					for(int x = 0; x < 8; ++x)
					{
						int oldVal = ((input[ti*16+y]>>(7-x))&1) | (((input[ti*16+y+8]>>(7-x))&1)<<1);
						int newVal = map[oldVal];
						output[ti*16+y] |= (byte)((newVal&1) << (7-x));
						output[ti*16+y+8] |= (byte)(((newVal>>1)&1) << (7-x));
					}
				}
			}
			
			return output;
		}
		
		private ulong[] _patterns;
		private ulong[] _patternsRX;
		private ulong[] _patternsRY;
		private ulong[] _patternsRXY;

		public List<byte> Encode(NesEncoderParameters parameters, byte[] input, Statistics externalStats)
		{
			int[][] mappings = new int[][] { 
				new int[]{ 0, 1, 2, 3 },
				new int[]{ 0, 2, 1, 3 },
				new int[]{ 0, 1, 3, 2 },
				new int[]{ 0, 2, 3, 1 },
				new int[]{ 0, 3, 1, 2 },
				new int[]{ 0, 3, 2, 1 } };

			int mappingCount = parameters.AllowColorRemap ? mappings.Length : 1;
			
			int bestIndex = -1;
			List<byte> best = null;
			for(int i = 0; i < mappingCount; ++i)
			{
				Statistics stats = new Statistics();
				List<byte> trial = TryEncode(RemapColors(input, mappings[i]), stats);
				if(best == null || trial.Count < best.Count)
				{
					bestIndex = i;
					best = trial;
					externalStats.Add(stats);
				}
			}
			
			best.Insert(0,(byte)bestIndex);
			
			return best;
		}
				
		public byte[] EncodeUBD(int pi)
		{
			int foundUpper = -1;
			int foundLower = -1;
			
			for(int offset = 0; offset < 256; offset++)
			{
				int ri = pi-offset-1;
				if(ri < 0)
					break;

				ulong rupper = _patterns[ri] & 0xFFFFFFFF00000000UL;
				ulong pupper = _patterns[pi] & 0xFFFFFFFF00000000UL;
				if(rupper == pupper)
				{
					foundUpper = offset;
					break;
				}
			}

			for(int offset = 0; offset < 256; offset++)
			{
				int ri = pi-offset-1;
				if(ri < 0)
					break;

				ulong rlower = _patterns[ri] & 0x00000000FFFFFFFFUL;
				ulong plower = _patterns[pi] & 0x00000000FFFFFFFFUL;
				if(rlower == plower)
				{
					foundLower = offset;
					break;
				}
			}
			
			if(foundUpper >= 0 && foundLower >= 0)
			{
				if(foundUpper < 8 && foundLower < 16)
				{
					return new byte[] { (byte)(0x80 + (foundUpper << 4) + foundLower) };
				}

				if(foundLower < 128)
				{
					return new byte[] { (byte)foundLower, (byte)foundUpper };
				}
			}

			return null;
		}
		
		public List<byte> TryEncode(byte[] input, Statistics stats)
		{
			List<byte> output = new List<byte>();
			int patternCount = input.Length / 8;
			Debug.Assert((input.Length & 7) == 0);
			
			stats._totalPatternCount += patternCount;

			// Convert patterns to 64-bit ulong primitive type. (8x8 bit)
			// Also make reversed copies to help costly O(n²) searches later.
			_patterns = new ulong[patternCount];
			_patternsRX = new ulong[patternCount];
			_patternsRY = new ulong[patternCount];
			_patternsRXY = new ulong[patternCount];

			for(int pi = 0; pi < patternCount; ++pi)
			{
				ulong p = Misc.ExtractPattern(input, pi);
				_patterns[pi] = p;
				_patternsRX[pi] = Misc.ReversePatternX(p);
				_patternsRY[pi] = Misc.ReversePatternY(p);
				_patternsRXY[pi] = Misc.ReversePatternXY(p);
			}

			ulong[] commonPatterns = { 0UL, ~0UL };
			int[] commonIndices = GetCommonPatterns();
			for(int i = 0; i < commonIndices.Length; ++i)
			{
				output.AddRange(BitConverter.GetBytes((ushort)commonIndices[i]));
			}
			
			int groupHeaderStart = 0;
			for(int pi = 0; pi < patternCount; ++pi)
			{
				PatternMode pm;
				
				// Start of 8 pattern group?
				if((pi & 7) == 0)
				{
					// Add empty group header
					groupHeaderStart = output.Count;
					output.Add(0);
					output.Add(0);
					output.Add(0);
				}
				
				// PatternMode.Common
				if(_patterns[pi] == commonPatterns[0])
				{
					pm = PatternMode.CommonA;
				}
				else if(_patterns[pi] == commonPatterns[1])
				{
					pm = PatternMode.CommonB;
				}
				else if(pi > 0 && _patterns[pi] == _patterns[pi-1])
				{
					pm = PatternMode.SameAsLast;
				}
				else if(pi > 0 && _patterns[pi] == ~_patterns[pi-1])	
				{
					pm = PatternMode.SameAsLastInverted;
				}					
				else
				{
					// 1) Row-Repeat encoded tile
					//
					// Remove repeated rows. Store which ones are explicit as 1's in a 1 byte tile header.
					//
					// RCR Header: T1234567
					// 		T: Tile is transposed				
					// 		1-7: Row numbers that are explicit (note: row 0 is always stored)		
					int rcrByteCount = Misc.GetRCRByteCount(_patterns[pi]);
					
					// 6-7) Row Difference encoding, find "best" earlier pattern and store differing rows.
					// 
					// RD header: xppppppp  (x=unused, p=pattern offset)
					//            01234567  0-7: Rows that are stored (n=# bits set)
					// Then follow "n" stored rows.
					PatternMode mode;
					byte[] rd = EncodeRD(pi, out mode);
					if(rd != null && rd.Length > 0 && rd.Length < rcrByteCount && rd.Length < 8)
					{
						if(mode == PatternMode.RD2)
						{
							if((rd[0] & 0x80) != 0)
								stats._mode67Counts[3]++;
							else
								stats._mode67Counts[2]++;
								
							pm = PatternMode.RD2;
						}
						else
						{
							if((rd[0] & 0x80) != 0)
								stats._mode67Counts[1]++;
							else
								stats._mode67Counts[0]++;
							
							pm = PatternMode.RD;
						}
	
						output.AddRange(rd);
					}
					else if(rcrByteCount < 8) // 8 is the cost of a raw pattern
					{
						pm = PatternMode.RCR;
						output.AddRange(Misc.EncodeRCR(_patterns[pi]));
					}
					else
					{
						// 0) Fallback: raw encoded tile
						pm = PatternMode.Raw;
						output.AddRange(BitConverter.GetBytes(_patterns[pi]));
					}
					
				}

				for(int i = 0; i < commonIndices.Length; ++i)
				{
					if(commonIndices[i] == pi)
						commonPatterns[i] = _patterns[pi];
				}

				int pmi = (int)pm;
				stats._patternModeCounts[pmi]++;

                int mask = 0x80 >> (pi & 7);
				output[groupHeaderStart+0] |= (byte)(((pmi & 4) != 0) ? mask : 0);
                output[groupHeaderStart+1] |= (byte)(((pmi & 2) != 0) ? mask : 0);
                output[groupHeaderStart+2] |= (byte)(((pmi & 1) != 0) ? mask : 0);
			}
						
			return output;
		}
	}
}
